/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.HashMap;

/**
 *
 * @author Santos
 */
public class DV {

    private HashMap<String, Integer> vizinhos; //string é a chave
    private HashMap<String, Integer> identificadores;
    private Integer vetorVizinho[];
    private int matriz[][];
    private String nomes[];
    private String noatual;
    private int posicaonoatual;
    private boolean mudou = false;
    private int quantidadedenos;
    static int INFINITO = 999999;
    private int recebeudovizinho = 0;
    private HashMap<Integer, Integer> anterior; //int para o nó, int para o anterior dele

    /**
     * Construtor que recebe o nome do nó, o vetor com os pesos deste nó até seus vizinhos e um vetor de string com os nomes do outros nós
     * @param noatual
     * @param vetorVizinho
     * @param nomes 
     */
    public DV(String noatual, Integer vetorVizinho[], String nomes[]) {//HashMap<String,Integer> nocorrente, int vetorVizinho[], String nomes[]){
        this.vetorVizinho = vetorVizinho;
        this.quantidadedenos = vetorVizinho.length;
        //vizinhos = nocorrente;
        vizinhos = new HashMap<String, Integer>();
        //anterior = new HashMap<String, Antecessor>();
        anterior = new HashMap<Integer, Integer>();
        identificadores = new HashMap<String, Integer>();

        this.noatual = noatual;
        this.nomes = nomes;
        this.matriz = new int[quantidadedenos][quantidadedenos];
        this.addvizinhosnoHashMap();
        this.recebeudovizinho = 1;
    }

    private void addvizinhosnoHashMap() {//se for infinito não é vizinho, os vizinhos deste noatual
        for (int i = 0; i < quantidadedenos; i++) {
            if (vetorVizinho[i] != 0 && vetorVizinho[i] != INFINITO) {
                vizinhos.put(nomes[i], i);  //add o nome e o id no vetor para cálculos
            }
            if (vetorVizinho[i] == 0) { //descobre o no atual
                noatual = nomes[i];
                //vizinhos.put(nomes[i], i);  //add o noatual, caso seja diferente do noatual é vizinho
                posicaonoatual = i;
            }
            identificadores.put(nomes[i], i);//adiciona todos os identificadores
            //if(vetorVizinho[i] != INFINITO)
            //  vizinhos.put(nomes[i], -1); //-1 não é vizinho
        }
        //inicializando a matriz
        for (int i = 0; i < quantidadedenos; i++) {
            //if(vetorVizinho[i] != INFINITO){
            matriz[posicaonoatual][i] = vetorVizinho[i];//recebe os pesos até os vizinhos
        }
        for (int i = 0; i < quantidadedenos; i++) {
            for (int j = 0; j < quantidadedenos; j++) {
                if (i != posicaonoatual) //todas as outrs linhas da tabela é infinita, ainda não conhecida
                {
                    matriz[i][j] = INFINITO;//recebe os pesos até os vizinhos
                }
            }
        }
    }//fim addvizinhosnoHashMap

    /**
     * Método que recebe um vetor de pesos de um nó vizinho e o nome do nó vizinho que mandou
     * @param novizinho
     * @param vetorVizinho 
     */
    public void recebevetordovizinho(String novizinho, Integer vetorVizinho[]) {
        int posicaonamatriz;
        posicaonamatriz = identificadores.get(novizinho);//posicaonamatriz = vizinhos.get(novizinho);
        this.recalculalinhavizinho(posicaonamatriz, vetorVizinho);
        this.bellmanford(posicaonamatriz, vetorVizinho);
    }

    private void recalculalinhavizinho(int posicaonamatriz, Integer vetorVizinho[]) {

        for (int i = 0; i < quantidadedenos; i++) {
            if (matriz[posicaonamatriz][i] == INFINITO) { //quando a linha do vizinho está toda infinito, é inicialmente
                matriz[posicaonamatriz][i] = vetorVizinho[i];
                //como é possivel chegar ao vizinho, vamos ver se é possivel chegar em outro nó através deste vizinho
            }
        }
    }

    private void bellmanford(int posicaonamatriz, Integer vetorVizinho[]) {
        //fixa-se no nó que enviou e testa até os outros
        int valormatriz, valornovo;
        for (int i = 0; i < quantidadedenos; i++) {
            if (i != posicaonoatual && i != posicaonamatriz) {// && matriz[posicaonamatriz][i] != 0){//não é este nó, nem este vizinho
                valormatriz = matriz[posicaonoatual][i];//matriz[posicaonamatriz][i];
                valornovo = matriz[posicaonoatual][posicaonamatriz] + matriz[posicaonamatriz][i];//vetorVizinho[i];////
                if (valornovo == this.minimo(valormatriz, valornovo)) {
                    mudou = true; //achamos um caminho menor
                    matriz[posicaonoatual][i] = valornovo;//
                    if (anterior.containsKey(i)) {
                        anterior.remove(i);
                        anterior.put(i, posicaonamatriz); //i tem posicaonamatriz como antecessor ou anterior
                    } else {
                        anterior.put(i, posicaonamatriz);
                    }
                }
            }
        }

    }

    private int minimo(int valormatriz, int valornovo) {
        //System.out.println("Método minimo: v1 = "+valormatriz+" v2 = "+valornovo);
        if (valormatriz < valornovo) {
            return valormatriz;
        } else {
            return valornovo;
        }
    }

    /**
     * Método que recebe o nome do nó de destino e retorna o nome do nó pra quem deve ser enviado o pacote.
     * Caso o nó passado como destino seja vizinho do nó que estar a enviar e não exista rota
     * menor para alcançar o destino o retorno será o próprio nó de destino
     * @param destino
     * @return 
     */
    public String paraquemenviar(String destino) {

        String ant, enviepara, dest = destino;
        //enviepramim = this.auxiliarnahoradeenviar(destino);
        while (true) {
            ant = this.auxiliarnahoradeenviar(dest);

            if (this.auxiliarnahoradeenviar(ant).equals(dest)) {//if(ant.equals(noatual)){
                enviepara = ant;//destino;
                break;
            }

            dest = ant;
        }
        return enviepara;
    }

    private String auxiliarnahoradeenviar(String destino) {
        int posicaodestino = -1;
        String noanterioradestino = " Não achei";
        boolean caminhoalternativo = false;
        //if(vizinhos.containsKey(destino))
        //  posicaodestino = vizinhos.get(destino); //aqui pegamos a posicao do nó com esse nome, caso seja vizinho
        //else
        posicaodestino = identificadores.get(destino);
        //naõ é vizinho
        //if()
        /*TINHA PROBLEMA AQUI*/
        int posicaoanteriordestino = -1;//não é vizinho e não tem anterior
        if (anterior.containsKey(posicaodestino)) {
            posicaoanteriordestino = anterior.get(posicaodestino);//retorna o anterior a esse nó
        }        //else{
        //if(vizinhos.containsKey(destino))
        // posicaoanteriordestino = vizinhos.get(destino);
        //}
        //vizinhos.get(String)
        for (String chave : vizinhos.keySet()) {
            if (vizinhos.get(chave) == posicaoanteriordestino) {
                noanterioradestino = chave;
                caminhoalternativo = true;
                break;
            }
            //System.out.println(string + "  " + vizinhos.get(string));
        }
        if (!caminhoalternativo) {//o destino é vizinho direto, sem caminho alternativo, é só enviar diretamente para ele
            for (String chave : vizinhos.keySet()) {
                if (vizinhos.containsKey(destino)) {
                    noanterioradestino = destino;
                    break;
                }
                //System.out.println(string + "  " + vizinhos.get(string));
            }
        }
        return noanterioradestino;
    }

    /**
     * Método que retorna o vetor de pesos do nó em questão
     * @return 
     */
    public Integer[] meuvetor() {
        Integer vetor[] = new Integer[quantidadedenos];
        for (int i = 0; i < quantidadedenos; i++) {
            vetor[i] = matriz[posicaonoatual][i];
        }
        return vetor;
    }


    /**
     * Método que retorna um booleano correspondente a mudança ou não no vetor de pesos do nó em questão
     * @return 
     */
    public boolean getmudou() {
        return mudou;
    }

    /**
     * Método utilizado para setar o valor da variável mudou
     * @param mudou 
     */
    public void setMudou(boolean mudou) {
        this.mudou = mudou;
    }

    @Override
    public String toString() {

        System.out.println(" Vetor vizinho de " + this.noatual + " ");
        for (int i = 0; i < this.vetorVizinho.length; i++) {
            System.out.print(" " + this.vetorVizinho[i] + " ");
        }
        System.out.println(" Nomes: ");
        for (int i = 0; i < this.nomes.length; i++) {
            System.out.printf(" %s ", this.nomes[i]);
        }
        System.out.println(" ");
        return "DV{" + '}';
    }

    /**
     * Método que retorna o vetor de pesos do nó em questão
     * @return 
     */
    public Integer[] getVetorVizinho() {
        return vetorVizinho;
    }
}
